package datastructure.graph.无向图;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @author MaoLin Wang
 * @description
 * @date 2020/8/27 2:43 下午
 */
public class BreadthFirstPaths {
    private final int start;
    private boolean[] marked;
    private int[] edgeTo;

    public BreadthFirstPaths(Graph graph,int start) {
        this.start = start;
        marked=new boolean[graph.getV()];
        edgeTo=new int[graph.getV()];
        bfs(graph,start);
    }

    private void bfs(Graph graph, int start) {
        Queue<Integer>queue=new LinkedList<>();
        queue.add(start);
        marked[start]=true;
        while (!queue.isEmpty()){
            Integer v = queue.poll();
            for (Integer w : graph.adj(v)) {
                if (!marked[w]){
                    queue.add(w);
                    edgeTo[w]=v;
                    marked[w]=true;
                }
            }
        }
    }
    public boolean hasPathTo(int v){
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v){
        if (!hasPathTo(v)){
            return null;
        }
        Stack<Integer> paths=new Stack<>();
        for (int i = v; i !=start ; i=edgeTo[i]) {
            paths.push(i);
        }
        paths.push(start);
        return paths;
    }

    public static void main(String[] args) {
        Graph graph=new Graph(7);
        graph.addEdge(0,4);
        graph.addEdge(0,  6);
        graph.addEdge(0,  2);
        graph.addEdge(2,5);
        graph.addEdge(2,1);
        graph.addEdge(2,3);
        graph.addEdge(2,4);
        graph.addEdge(3,5);
        graph.addEdge(3,4);
        graph.addEdge(5,6);

        BreadthFirstPaths dfs=new BreadthFirstPaths(graph,0);
        Iterable<Integer> paths = dfs.pathTo(5);
        for (Integer i:paths){
            System.out.println(i.toString());
        }
    }
}
